Low-density parity check (LDPC) codes are block codes that can provide highly efficient error correction coding (approaching the Shannon limit for large block sizes). LDPC codes introduce redundancy into the transmitted code word in such a way that the parity check matrix is sparse (i.e., has few 1's in each row and column). This enables efficient decoding algorithms based on belief propagation.
Typical decoding uses a two stage process based on the Tanner graph of the code. Variable node computation units pass messages to check node computation units indicating likelihood for current variable values. Check node computation units then determine update messages which are passed back to the variable node computation units. Each check node receives messages from those variable computation nodes that are a part of its parity check equation, and sends update messages back to the variable computation nodes. The variable nodes recompute variable likelihoods. The process iterates until the code word passes parity check or a preset number of iterations passes.
Unfortunately, the decoding process is expensive in terms of memory and processing time. A decoder can be partitioned to perform parallel operations by providing separate computation units for each variable and check node. A parallel implementation can be very fast, however, interconnection between the many computation units can be difficult. A parallel implementation also uses a large amount of real estate within an integrated circuit or gate array.
Alternately, a serial decoder can be implemented using a single variable computation unit and a single check computation unit. Interconnection between the computation units is straightforward and real estate usage is relatively small. Processing is slow, however, as the variable computation unit and check computation unit must each sequentially cycle through all of the nodes.
Hybrid serial-parallel implementations are known, where a number of variable computation and a number of check computations are multiplexed for processing of a subset of the variable nodes and check nodes. A serial-parallel implementation provides a tradeoff between speed and real estate requirements. Unfortunately, serial-parallel implementations can be difficult to design. In particular, interconnection can be difficult if check node computation units need connections to every variable node computation unit. Memory storage for variable likelihoods and check node messages can be difficult, as memories typically only provide one or two read/write ports, and memory conflicts can occur. When the design is constrained by additional requirements (e.g., a particular gate array architecture or silicon real-estate limitation) design requirements can be difficult to meet.
As a particular example, in designing an LDPC decoder for implementation in a field programmable gate array (FPGA), clock rates are limited relative to custom integrated circuit designs. This makes serial implementations too slow in some applications. Parallel implementations, however, result in routing complexity difficult to accommodate. Straightforward semi-parallel implementations can require larger amounts of memory than available on an FPGA.